//+------------------------------------------------------------------+
//|                                                      HashMap.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic/Interfaces/IMap.h>
#include <Generic/Interfaces/IEqualityComparer.h>
#include <Generic/Internal/DefaultEqualityComparer.h>
#include <Generic/Interfaces/IComparable.h>
#include <Generic/Internal/CompareFunction.h>
#include "HashSet.h"

//+------------------------------------------------------------------+
//| Entry<TKey, TValue> 结构体：CHashMap 内部存储单元                |
//| 核心定位：哈希映射的底层键值对存储结构，继承自 Slot<TValue>（提供基础存储能力） |
//| 用途：封装单个键值对数据，用于哈希表的桶（Bucket）与链表存储        |
//+------------------------------------------------------------------+
template<typename TKey, typename TValue>
struct Entry : public Slot<TValue>
  {
public:
   TKey              key;                // 键（唯一标识，用于哈希查找）
   /**
    * @brief 默认构造函数：初始化键为默认空值
    */
                     Entry(void) : key((TKey)NULL) {}
  };

//+------------------------------------------------------------------+
//| CKeyValuePair<TKey, TValue> 类：键值对封装类                     |
//| 核心定位：实现 IComparable 接口，封装独立的键值对数据，支持比较与克隆 |
//| 用途：作为哈希映射对外暴露的键值对单元，便于数据传递与操作          |
//+------------------------------------------------------------------+
template<typename TKey, typename TValue>
class CKeyValuePair : public IComparable<CKeyValuePair<TKey, TValue>*>
  {
protected:
   TKey              m_key;              // 存储键
   TValue            m_value;            // 存储值

public:
   /**
    * @brief 默认构造函数：初始化空键值对
    */
                     CKeyValuePair(void) {}

   /**
    * @brief 带参构造函数：通过指定键和值初始化键值对
    * @param key [in] 键（唯一标识）
    * @param value [in] 与键关联的值
    */
                     CKeyValuePair(TKey key, TValue value) : m_key(key), m_value(value) {}

   /**
    * @brief 析构函数：清理键值对资源
    */
                    ~CKeyValuePair(void) {}

   //----------------------------------------------------------------
   // 键值访问接口
   //----------------------------------------------------------------
   /**
    * @brief 获取键值对中的键
    * @return TKey - 键的当前值
    */
   TKey              Key(void) { return(m_key); }

   /**
    * @brief 设置键值对中的键
    * @param key [in] 新的键值（需确保唯一性）
    */
   void              Key(TKey key) { m_key = key; }

   /**
    * @brief 获取键值对中的值
    * @return TValue - 值的当前值
    */
   TValue            Value(void) { return(m_value); }

   /**
    * @brief 设置键值对中的值
    * @param value [in] 新的值
    */
   void              Value(TValue value) { m_value = value; }

   //----------------------------------------------------------------
   // 克隆与比较接口
   //----------------------------------------------------------------
   /**
    * @brief 克隆当前键值对实例（创建新对象）
    * @return CKeyValuePair<TKey, TValue>* - 新的键值对克隆体
    * @note 克隆对象与原对象数据完全一致，但内存地址独立
    */
   CKeyValuePair<TKey, TValue>* Clone(void) { return new CKeyValuePair<TKey, TValue>(m_key, m_value); }

   /**
    * @brief 与另一个键值对比较（基于键的比较）
    * @param pair [in] 待比较的键值对
    * @return int - 比较结果：
    *               <0：当前键 < 目标键；
    *               =0：当前键 == 目标键；
    *               >0：当前键 > 目标键
    * @note 依赖 ::Compare() 函数实现具体比较逻辑
    */
   int               Compare(CKeyValuePair<TKey, TValue>* pair) { return ::Compare(m_key, pair->m_key); }

   /**
    * @brief 判断与另一个键值对是否相等（基于键的相等性）
    * @param pair [in] 待判断的键值对
    * @return bool - 相等结果：true=键相同；false=键不同
    * @note 依赖 ::Equals() 函数实现键的相等性判断
    */
   bool              Equals(CKeyValuePair<TKey, TValue>* pair) { return ::Equals(m_key, pair->m_key); }

   /**
    * @brief 计算当前键值对的哈希码（基于键的哈希值）
    * @return int - 32位哈希码
    * @note 依赖 ::GetHashCode() 函数实现键的哈希计算，确保键相同则哈希码相同
    */
   int               HashCode(void) { return ::GetHashCode(m_key); }
  };

//+------------------------------------------------------------------+
//| CKeyValuePairComparer<TKey, TValue> 类：键值对比较器             |
//| 核心定位：实现 IComparer 接口，将键的比较器适配为键值对的比较器     |
//| 用途：解决“基于键的比较逻辑”与“键值对比较接口”的适配问题          |
//+------------------------------------------------------------------+
template<typename TKey, typename TValue>
class CKeyValuePairComparer : public IComparer<CKeyValuePair<TKey, TValue>*>
  {
private:
   IComparer<TKey>*  m_comparer;         // 底层键的比较器

public:
   /**
    * @brief 构造函数：通过键的比较器初始化键值对比较器
    * @param comparer [in] 键的比较器（实现 IComparer<TKey> 接口）
    */
                     CKeyValuePairComparer(IComparer<TKey>* comparer) { m_comparer = comparer; }

   /**
    * @brief 比较两个键值对（基于键的比较结果）
    * @param x [in] 第一个键值对
    * @param y [in] 第二个键值对
    * @return int - 比较结果（同 CKeyValuePair::Compare() 的返回值规则）
    * @note 实际调用底层键比较器的 Compare() 方法，比较两个键值对的键
    */
   int               Compare(CKeyValuePair<TKey, TValue>* x, CKeyValuePair<TKey, TValue>* y) { return(m_comparer->Compare(x->Key(), y->Key())); }
  };

//+------------------------------------------------------------------+
//| CHashMap<TKey, TValue> 类：哈希映射实现类                        |
//| 核心定位：实现 IMap 接口，基于哈希表实现键值对存储，支持高效的键查找 |
//| 核心特性：                                                      |
//|  1. 键唯一性：同一键仅对应一个值，重复添加会失败；                |
//|  2. 高效操作：查找/添加/删除时间复杂度接近 O(1)（哈希表特性）；     |
//|  3. 冲突处理：通过链表法解决哈希冲突（同一桶内元素形成链表）；      |
//|  4. 动态扩容：负载因子过高时自动扩容，维持高效查找性能；           |
//| 适用场景：所有需要通过唯一键快速访问数据的场景（如订单ID→订单信息、品种→价格） |
//+------------------------------------------------------------------+
template<typename TKey, typename TValue>
class CHashMap : public IMap<TKey, TValue>
  {
protected:
   int               m_buckets[];        // 哈希桶数组（存储链表头索引，实现冲突处理）
   Entry<TKey, TValue> m_entries[];      // 键值对存储数组（所有键值对实际存储位置）
   int               m_count;            // 总键值对数量（含已删除的空闲项）
   int               m_capacity;         // 哈希表容量（桶的数量，为质数，优化哈希分布）
   int               m_free_list;        // 空闲项链表头（复用已删除的存储位置，减少内存分配）
   int               m_free_count;       // 空闲项数量（记录可复用的存储位置数）
   IEqualityComparer<TKey>* m_comparer;  // 键的相等性比较器（判断键是否相同）
   bool              m_delete_comparer;  // 是否自动释放比较器内存（构造时传入外部比较器则为false）

public:
   //----------------------------------------------------------------
   // 构造与析构接口
   //----------------------------------------------------------------
   /**
    * @brief 默认构造函数：创建空哈希映射，使用默认容量和默认键比较器
    * @note 默认容量由内部逻辑确定，默认比较器为 CDefaultEqualityComparer<TKey>
    */
                     CHashMap(void);

   /**
    * @brief 指定容量构造函数：创建空哈希映射，使用指定初始容量和默认键比较器
    * @param capacity [in] 初始容量（哈希桶数量，实际会调整为最近的质数）
    * @note 提前指定合适容量可减少后续扩容次数，提升性能
    */
                     CHashMap(const int capacity);

   /**
    * @brief 指定比较器构造函数：创建空哈希映射，使用默认容量和指定键比较器
    * @param comparer [in] 键的相等性比较器（实现 IEqualityComparer<TKey> 接口）
    * @note 适用于自定义键的相等性判断逻辑（如不区分大小写的字符串键）
    */
                     CHashMap(IEqualityComparer<TKey>* comparer);

   /**
    * @brief 容量+比较器构造函数：创建空哈希映射，使用指定初始容量和键比较器
    * @param capacity [in] 初始容量（哈希桶数量，调整为最近的质数）
    * @param comparer [in] 键的相等性比较器（实现 IEqualityComparer<TKey> 接口）
    */
                     CHashMap(const int capacity, IEqualityComparer<TKey>* comparer);

   /**
    * @brief 从映射构造函数：创建哈希映射并复制指定 IMap 的所有键值对，使用默认比较器
    * @param map [in] 源映射（实现 IMap<TKey, TValue> 接口，如另一个 CHashMap）
    */
                     CHashMap(IMap<TKey, TValue>* map);

   /**
    * @brief 映射+比较器构造函数：创建哈希映射并复制指定 IMap 的所有键值对，使用指定比较器
    * @param map [in] 源映射（实现 IMap<TKey, TValue> 接口）
    * @param comparer [in] 键的相等性比较器（实现 IEqualityComparer<TKey> 接口）
    */
                     CHashMap(IMap<TKey, TValue>* map, IEqualityComparer<TKey>* comparer);

   /**
    * @brief 析构函数：清理哈希映射资源
    * @note 若比较器为内部创建（使用默认比较器），则自动释放比较器内存
    */
                    ~CHashMap(void);

   //----------------------------------------------------------------
   // 键值对添加接口
   //----------------------------------------------------------------
   /**
    * @brief 添加键值对对象到哈希映射
    * @param pair [in] 待添加的键值对（CKeyValuePair<TKey, TValue> 实例）
    * @return bool - 添加结果：true=添加成功（键不存在）；false=添加失败（键已存在或键值对为NULL）
    */
   bool              Add(CKeyValuePair<TKey, TValue>* pair);

   /**
    * @brief 添加指定键和值到哈希映射
    * @param key [in] 键（唯一标识，需支持哈希计算和相等性判断）
    * @param value [in] 与键关联的值
    * @return bool - 添加结果：true=添加成功（键不存在）；false=添加失败（键已存在）
    */
   bool              Add(TKey key, TValue value);

   //----------------------------------------------------------------
   // 基础信息与包含性检查接口
   //----------------------------------------------------------------
   /**
    * @brief 获取当前哈希映射中的有效键值对数量（排除空闲项）
    * @return int - 有效键值对数量（≥0，空映射返回0）
    */
   int               Count(void) { return(m_count - m_free_count); }

   /**
    * @brief 获取当前使用的键相等性比较器
    * @return IEqualityComparer<TKey>* - 键比较器实例（NULL 表示未设置）
    */
   IEqualityComparer<TKey>* Comparer(void) const { return(m_comparer); }

   /**
    * @brief 检查哈希映射是否包含指定键值对
    * @param item [in] 待检查的键值对（CKeyValuePair<TKey, TValue> 实例）
    * @return bool - 检查结果：true=包含（键存在且值匹配）；false=不包含
    */
   bool              Contains(CKeyValuePair<TKey, TValue>* item);

   /**
    * @brief 检查哈希映射是否包含指定的键值组合
    * @param key [in] 待检查的键
    * @param value [in] 待检查的值
    * @return bool - 检查结果：true=包含（键存在且对应值匹配）；false=不包含
    */
   bool              Contains(TKey key, TValue value);

   /**
    * @brief 检查哈希映射是否包含指定的键
    * @param key [in] 待检查的键
    * @return bool - 检查结果：true=键存在；false=键不存在
    * @note 内部调用 FindEntry() 查找键，效率接近 O(1)
    */
   bool              ContainsKey(TKey key);

   /**
    * @brief 检查哈希映射是否包含指定的值
    * @param value [in] 待检查的值
    * @return bool - 检查结果：true=值存在；false=值不存在
    * @note 需遍历所有键值对，时间复杂度 O(n)，效率低于 ContainsKey()
    */
   bool              ContainsValue(TValue value);

   //----------------------------------------------------------------
   // 批量复制接口
   //----------------------------------------------------------------
   /**
    * @brief 将哈希映射中的所有键值对复制到键值对数组
    * @param dst_array [out] 目标键值对数组（需提前分配空间，或由方法自动扩容）
    * @param dst_start [in] 目标数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的键值对数量（≤ Count()）
    * @note 复制的是键值对的克隆体，修改目标数组元素不影响原映射
    */
   int               CopyTo(CKeyValuePair<TKey, TValue>*& dst_array[], const int dst_start=0);

   /**
    * @brief 将哈希映射中的键和值分别复制到两个独立数组
    * @param dst_keys [out] 目标键数组（存储所有键）
    * @param dst_values [out] 目标值数组（存储所有值，与键数组按索引对应）
    * @param dst_start [in] 数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的键值对数量（≤ Count()）
    * @note 键数组与值数组的索引一一对应（dst_keys[i] 对应 dst_values[i]）
    */
   int               CopyTo(TKey &dst_keys[], TValue &dst_values[], const int dst_start=0);

   //----------------------------------------------------------------
   // 清理与删除接口
   //----------------------------------------------------------------
   /**
    * @brief 清空哈希映射中的所有键值对（释放内存，重置状态）
    * @note 清空后容量重置为0，所有键值对数据被删除，空闲项链表清空
    */
   void              Clear(void);

   /**
    * @brief 从哈希映射中删除指定键值对
    * @param item [in] 待删除的键值对（CKeyValuePair<TKey, TValue> 实例）
    * @return bool - 删除结果：true=删除成功（键存在且值匹配）；false=删除失败
    */
   bool              Remove(CKeyValuePair<TKey, TValue>* item);

   /**
    * @brief 从哈希映射中删除指定键对应的键值对
    * @param key [in] 待删除的键
    * @return bool - 删除结果：true=删除成功（键存在）；false=删除失败（键不存在）
    * @note 删除后键对应的存储位置变为空闲项，可被后续添加复用
    */
   bool              Remove(TKey key);

   //----------------------------------------------------------------
   // 键值访问接口
   //----------------------------------------------------------------
   /**
    * @brief 通过键安全获取对应的值
    * @param key [in] 用于查找的键
    * @param value [out] 输出参数，接收找到的值（仅当返回 true 时有意义）
    * @return bool - 获取结果：true=键存在，成功获取值；false=键不存在
    * @note 核心高效操作，时间复杂度接近 O(1)
    */
   bool              TryGetValue(TKey key, TValue &value);

   /**
    * @brief 通过键安全修改对应的值
    * @param key [in] 用于定位的键
    * @param value [in] 待设置的新值
    * @return bool - 修改结果：true=键存在，成功修改值；false=键不存在，修改失败
    */
   bool              TrySetValue(TKey key, TValue value);

private:
   //----------------------------------------------------------------
   // 内部辅助接口（不对外暴露）
   //----------------------------------------------------------------
   /**
    * @brief 初始化哈希映射容量（创建桶数组和存储数组）
    * @param capacity [in] 目标容量（实际会调整为最近的质数，优化哈希分布）
    */
   void              Initialize(const int capacity);

   /**
    * @brief 调整哈希映射容量（扩容或缩容，重建哈希桶结构）
    * @param new_size [in] 新容量（需为质数）
    * @return bool - 调整结果：true=容量调整成功；false=调整失败（如内存不足）
    * @note 扩容时会重新计算所有键的哈希值，分配到新的桶中，解决负载过高问题
    */
   bool              Resize(int new_size);

   /**
    * @brief 查找指定键对应的存储项索引
    * @param key [in] 待查找的键
    * @return int - 查找结果：≥0 表示找到的存储项索引；-1 表示未找到
    * @note 内部通过哈希计算定位桶，再遍历桶内链表查找键，是所有键相关操作的基础
    */
   int               FindEntry(TKey key);

   /**
    * @brief 插入键值对（内部统一实现添加和修改逻辑）
    * @param key [in] 待插入的键
    * @param value [in] 待插入的值
    * @param add [in] 操作类型标记：true=仅添加（键不存在时成功）；false=仅修改（键存在时成功）
    * @return bool - 插入结果：true=操作成功；false=操作失败（如添加时键已存在）
    */
   bool              Insert(TKey key, TValue value, const bool add);

   /**
    * @brief 哈希冲突阈值：单个桶内允许的最大冲突次数（超过则触发扩容）
    * @note 静态成员，默认值为8，用于平衡冲突处理效率与扩容频率
    */
   static int        m_collision_threshold;
  };

//+------------------------------------------------------------------+
//| 静态成员初始化：哈希冲突阈值默认值为8                            |
//+------------------------------------------------------------------+
template<typename TKey, typename TValue>
int CHashMap<TKey, TValue>::m_collision_threshold = 8;
//+------------------------------------------------------------------+